package TanXin;

import java.util.Arrays;
import java.util.Comparator;
import java.util.PriorityQueue;

public class OtherTest {
    //    给你一个字符串数组,你拼接出一个最长的字符串
    public static class MyCompare implements Comparator<String > {

        @Override
        public int compare(String o1, String o2) {
            //判断字典序,而且选出来那个字典序结合后小
            return (o1+o2).compareTo(o2+o1);
        }
    }
    public static String lowestString(String[] strs){
        if (strs == null || strs.length == 0){
            return "";
        }
        Arrays.sort(strs,new MyCompare());
        String res="";
        for (int i = 0; i < strs.length; i++) {
            res+=strs[i];
        }
        return res;
    }
    //分割金条问题
    public static int lessMoney(int[] arr){
        PriorityQueue<Integer> queue=new PriorityQueue<>();
        for (int i = 0; i < arr.length; i++) {
            queue.add(arr[i]);
        }
        int sum=0;
        int cur=0;
        /*哈夫曼树,每次找到2个最小,结合成一个值,扔回去*/
        while (queue.size() > 1){
            cur = queue.poll()+queue.poll();
            sum += cur;
            queue.add(cur);
        }
        return sum;
    }

    /****************************************************** /
     */
    private static class Node{
        public int p;//利润
        public int c;//花费

        public Node(int p, int c) {
            this.p = p;
            this.c = c;
        }
    }
    private static class MinCostCompare implements Comparator<Node>{

        @Override
        public int compare(Node o1, Node o2) {
            return o1.c-o2.c;
        }
    }
    private static class MaxProfitCompare implements Comparator<Node>{

        @Override
        public int compare(Node o1, Node o2) {
            return o2.p-o1.p;//组建一个由利润组成的大根堆
        }
    }
    public static int findMaximizedCapital(int k,int w,int[] Profits,int[] captal){
        /*k 最多做几个项目, w 初始资金,Profits项目的花费 , captal所得的利润*/
        PriorityQueue<Node> minQ=new PriorityQueue<>(new MinCostCompare());
        PriorityQueue<Node> maxQ=new PriorityQueue<>(new MaxProfitCompare());

        for (int i = 0; i < Profits.length; i++) {
            minQ.add(new Node(Profits[i],captal[i]));
        }
        for (int i = 0; i < k; i++) {
            //解锁所有我现在能解锁的项目
            while (!minQ.isEmpty() && minQ.peek().c <= w){
                maxQ.add(minQ.poll());
            }
            if (maxQ.isEmpty()){
                //没项目可以做了,坐不了
                return w;
            }
            w+=maxQ.poll().p;//加上所获得的利润
        }
        return w;
    }
    //n皇后问题
    public static int num1(int n){
        if (n < 1)return 0;
        //record[i] 代表 i 行 的皇后,放在了那一列
        int[] record = new int[n];
        return process(0,record,n);
    }
    //record[0,i-1]的皇后,一定不共行,不共列,不共斜线
    //目前来到了第 i 行,record[0,i-1]表示之前的行,放了的皇后的位置
    //n 表示整体一共多少行
    //返回值是,摆完所有的皇后,合理的摆法有多少种
    public static int process(int i,int[] record ,int n){
        if (i == n){//终止行
            return 1;
        }
        int res =0;
        for (int j=0; j < n;j++){//当前行在i行,尝试i行所有的列
            //当前 i 行的 皇后,放在j列,判断是否会和之前的皇后, 共行 共 列 共斜线
            //如果是,则认为有效
            //如果不是 ,认为无效
            if (isValid(record,i,j)){
                record[i]=j;
                res+=process(i+1,record,n);
            }
        }
        return res;
    }
    //record[0...i-1]需要看,record[i...]不需要看
    //如果i行皇后,放到了j列, 是否有效
    public static boolean isValid(int[] record,int i,int j){
        for (int k = 0; k < i; k++) {
            if (j == record[k] || Math.abs(record[k] -j) == Math.abs(i-k)){
                //1,不共列, 2不能成45度
                return false;
            }
        }
        return true;
    }
    // 中位数问题
    public static int ZWS(int[] arr){
        if (arr == null)return -1;
        if (arr.length == 1)return arr[0];
        PriorityQueue<Integer> q1 = new PriorityQueue<>((o1, o2) -> o1-o2);//小根堆
        PriorityQueue<Integer> q2 = new PriorityQueue<>((o1, o2) -> o2-o1);//大根堆
        q2.offer(arr[0]);
        for (int i = 1; i < arr.length; i++) {
            if (arr[i] > q2.peek()){
                q1.offer(arr[i]);
            }else {
                q2.offer(arr[i]);
            }
            if (Math.abs(q1.size()-q2.size()) >= 2 && q1.size() > q2.size()) {
                q2.offer(q1.poll());
            }
            if (Math.abs(q1.size()-q2.size()) >= 2 && q2.size() > q1.size()){
                q1.offer(q2.poll());
            }
        }
        return q1.size()>q2.size()?q1.poll():q2.poll();
    }



}
